package 组合总和III;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: AirMan
 * @date: 2025/4/11 13:07
 * @description: 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
 * 说明：
 * 所有数字都是正整数。
 * 解集不能包含重复的组合。
 * 示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]
 * 示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
 */
public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        // 回溯
        // 回溯的参数：n，k，startIndex，result，当前的path
        // 回溯的返回值：void
        // 回溯的终止条件：path.size() == k && pathSum == n
        // 单层回溯的逻辑：9就是for循环的最大次数(只能使用1-9之间的数字)，k就是递归的深度。
        // 递归过程中出现的情况：
        // ① path.size() == k && pathSum == n 表示找到了一个组合方法，且后续分支需要剪掉（等价②）
        // ② path.size() == k && pathSum > n 终止该路径的搜索，后续树的分支一定都是不满足条件的
        // ③ pathSum >= n 终止该路径的搜索，后续树的分支一定也都是不满足条件的
        // ④ 回溯搜索还需要的路径数 > 横向遍历for循环的数量，后续的分支一定不能满足 path.size() == k

        backtracking(k, n, 1);
        return result;
    }

    public List<List<Integer>> result = new ArrayList<>();
    public List<Integer> path = new ArrayList<>();
    int pathSum = 0;

    public void backtracking(int k, int n, int startIndex) {

        if (path.size() == k) {
            if (pathSum == n) {
                result.add(new ArrayList<>(path));
                return;
            }
        }
        // 剪枝 ④
        for (int i = startIndex; i <= 10 - k + path.size(); i++) {
            // 处理当前值
            path.add(i);
            pathSum += i;
            // 剪枝
            if ((path.size() > k) || (path.size() == k && pathSum > n) || pathSum > n) {
                pathSum -= i;
                path.remove(path.size() - 1);
                continue;
            }
            // 从当前值继续进行递归搜索
            backtracking(k, n, i + 1);
            // 撤销当前值，进行回溯
            pathSum -= i;
            path.remove(path.size() - 1);
        }
    }
}
